Solutions of an LPP: Feasible and Optimal

Feasible Solutions: Definition and Properties

Definition of Feasible Solution

A Feasible Solution to a Linear Programming Problem (LPP) is a set of values for the decision variables, say $x_1, x_2, \ldots, x_n$, that satisfies all the constraints of the problem simultaneously. This includes both the structural constraints (inequalities or equations representing resource limitations, requirements, etc.) and the non-negativity restrictions (if applicable, typically $x_i \geq 0$ for all $i$).

In the context of a two-variable LPP (with decision variables $x$ and $y$), a feasible solution corresponds to any point $(x, y)$ in the coordinate plane that lies within or on the boundary of the feasible region. The feasible region itself is the set of all such feasible solutions.

Properties of Feasible Solutions

• Satisfaction of Constraints: The fundamental property is that every feasible solution adheres to all the given constraints and non-negativity conditions without violation.
• Membership in Feasible Region: By definition, the collection of all feasible solutions forms the feasible region of the LPP. Any point outside this region is not a feasible solution.
• Not Necessarily Optimal: A feasible solution is simply a potential candidate solution that respects the problem's rules. It is not guaranteed to be the best possible solution (the one that optimizes the objective function). The optimal solution must be a feasible solution, but not all feasible solutions are optimal.
• Existence: An LPP may have:
  • Exactly one feasible solution (if the feasible region is a single point).
  • Infinitely many feasible solutions (this is the most common scenario when a feasible region exists and is not just a single point, especially with continuous variables).
  • No feasible solutions (if the constraints are contradictory, resulting in an empty feasible region; in this case, the LPP is termed **infeasible**).
• Basis for Optimization: The process of solving an LPP involves two main steps: first, identifying the set of all feasible solutions (the feasible region), and second, searching within this set to find the optimal solution(s) that maximise or minimise the objective function.

The diagram above illustrates a typical feasible region (the shaded area). Any point located within this shaded area or along its boundary lines is considered a feasible solution because its coordinates $(x, y)$ satisfy all the linear inequalities that define the region.

Example of a Feasible Solution

Answer:

Infeasible Solutions: Definition

Definition of Infeasible Solution

An Infeasible Solution to a Linear Programming Problem (LPP) is a set of values for the decision variables ($x_1, x_2, \ldots, x_n$) that violates at least one of the constraints or non-negativity restrictions specified in the problem formulation.

Graphically, for a two-variable LPP, an infeasible solution corresponds to any point $(x, y)$ in the coordinate plane that lies outside the feasible region. Such a point does not satisfy the conditions imposed by one or more constraints, making it an invalid or impossible solution in the context of the problem.

These points represent combinations of decision variable values that cannot be achieved under the given circumstances or limitations, such as exceeding available resources or failing to meet minimum production quotas.

Distinction: Infeasible Solution vs. Infeasible LPP

It is crucial to differentiate between an "infeasible solution" and an "infeasible LPP":

• Infeasible Solution: This refers to a specific point or set of variable values that lies outside the feasible region. Most LPPs with a non-empty feasible region will still have an infinite number of infeasible solutions (all the points in the plane that are not in the feasible region).
• Infeasible LPP: This describes the overall LPP model when no feasible solution exists at all. In this case, the feasible region is an empty set. This scenario arises when the set of constraints is contradictory or inconsistent, making it impossible to find any combination of decision variables that satisfies all conditions simultaneously. An infeasible LPP has no solution, including no optimal solution.

Example of an Infeasible Solution

Answer:

Example of an Infeasible LPP

Answer:

Optimal Feasible Solution: Definition

Definition of Optimal Feasible Solution

An Optimal Feasible Solution (often simply called the Optimal Solution) to a Linear Programming Problem (LPP) is a specific feasible solution that yields the best possible value for the objective function. "Best possible" means the maximum value if the objective is to maximize, and the minimum value if the objective is to minimize.

Formally, a feasible solution $(x_1^*, x_2^*, \ldots, x_n^*)$ is an optimal feasible solution if:

1. It is a feasible solution, meaning it satisfies all constraints and non-negativity restrictions of the LPP.
2. The value of the objective function, $Z(x_1^*, x_2^*, \ldots, x_n^*)$, is the optimal value. This means:
   • If the objective is to maximize $Z$, then $Z(x_1^*, \ldots, x_n^*) \geq Z(x_1, \ldots, x_n)$ for all other feasible solutions $(x_1, \ldots, x_n)$.
   • If the objective is to minimize $Z$, then $Z(x_1^*, \ldots, x_n^*) \leq Z(x_1, \ldots, x_n)$ for all other feasible solutions $(x_1, \ldots, x_n)$.

In essence, among all the combinations of decision variable values that are allowed by the constraints (i.e., all feasible solutions), the optimal feasible solution is the one that achieves the specified goal (maximum profit, minimum cost, etc.).

Properties and Location of Optimal Solutions

• Feasibility is Essential: An optimal solution must always be a feasible solution. If a solution violates any constraint, it cannot be the optimal solution, even if it yields a better value for the objective function when constraints are ignored.
• Location (Fundamental Theorem): A cornerstone of linear programming is the theorem stating that if an LPP has an optimal solution, then at least one such optimal solution must exist at a vertex or corner point of the feasible region. This dramatically simplifies the search for the optimum.
• Uniqueness or Multiplicity: An LPP can have:
  • A unique optimal solution (only one feasible point achieves the best objective function value).
  • Multiple optimal solutions (more than one feasible point achieves the same best objective function value). If there are multiple optimal solutions, they will all yield the *same* optimal value for the objective function. Graphically, this occurs when the objective function line is parallel to a boundary edge of the feasible region, and this edge contains two or more optimal vertices. In such a case, all points on the line segment connecting these optimal vertices are also optimal solutions.
• Non-Existence: An LPP may not have an optimal solution if:
  • It is **infeasible** (the feasible region is empty, so no feasible solution exists).
  • It is **unbounded** (the objective function can be increased indefinitely in a maximization problem, or decreased indefinitely in a minimization problem, within the feasible region).

The primary goal in solving an LPP is to identify this optimal feasible solution(s) and determine the corresponding optimal value of the objective function Z.

Example of an Optimal Feasible Solution

Answer:

Vertices (Corner Points) of the Feasible Region

Definition of Vertices (Corner Points)

A vertex or corner point of the feasible region in a graphical representation of a two-variable LPP is a point in the coordinate plane where two or more boundary lines of the feasible region intersect. These points are the "corners" of the polygonal feasible region (if bounded) or the corner points bordering an unbounded feasible region.

Each constraint inequality in an LPP defines a half-plane. The feasible region is the intersection of all these half-planes (including those from non-negativity restrictions like $x \geq 0$ and $y \geq 0$). The boundary of each half-plane is a straight line. The vertices of the feasible region are precisely the points where these boundary lines intersect, provided the intersection point lies within or on the boundary of the feasible region defined by all other constraints.

In the image above, the shaded area represents the feasible region. The points where the lines forming its boundary meet are the vertices.

Method for Finding Vertices

Vertices are determined by finding the points of intersection of the linear equations that form the boundaries of the feasible region. For a two-variable LPP, the steps typically involve:

1. Convert each inequality constraint into a linear equation by replacing the inequality sign ($\leq, \geq, <, >$) with an equality sign ($=$).
2. Identify pairs of these linear equations whose intersection points could potentially be vertices of the feasible region. These pairs usually correspond to lines that form adjacent boundaries of the feasible region.
3. Solve the system of equations for each chosen pair to find the coordinates $(x, y)$ of the intersection point. Standard methods like substitution or elimination can be used.
4. For each intersection point found, verify if it satisfies all the original constraints (including non-negativity). If a point satisfies all constraints, it is a vertex of the feasible region. Intersection points that lie outside the feasible region (violating one or more constraints) are not vertices of the feasible region, even though they are intersection points of the boundary lines.

Significance: The Corner Point Theorem

Vertices are of paramount importance in Linear Programming because of the **Fundamental Theorem of Linear Programming**, also known as the **Corner Point Theorem**. It states:

Theorem: If an optimal solution (maximum or minimum value of the objective function) exists for a Linear Programming Problem with a feasible region that is a convex polygon, then the optimal solution must occur at one (or more) of the vertices (corner points) of the feasible region.

This powerful theorem provides the basis for the widely used **Corner Point Method** (or Extreme Point Method) for solving LPPs, especially graphically. Instead of evaluating the objective function at every single point in the feasible region (which is impossible as there are infinitely many), the theorem tells us we only need to check the finite number of vertices. The optimal value must lie among the values calculated at these corners.

The steps derived from this theorem for solving a two-variable LPP graphically are:

1. Graph the feasible region.
2. Identify and find the coordinates of all the vertices of the feasible region.
3. Evaluate the objective function $Z$ at each vertex.
4. For a maximization problem, the vertex yielding the largest value of $Z$ is the optimal feasible solution. For a minimization problem, the vertex yielding the smallest value of $Z$ is the optimal feasible solution. The corresponding value of $Z$ is the optimal value.

Note: For unbounded feasible regions, an optimal solution may or may not exist. If it exists, it will still be at a corner point.

Example of Finding Vertices

Answer: